/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann - Tübingen, Germany 
 * Niko Schenk - Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */

/*
 * http://www.cs.princeton.edu/~rs/cs226/sorts/UnionFind.java
 * Copyright © 2000–2011, Robert Sedgewick and Kevin Wayne. 
 * Last updated: Sat Feb 26 10:07:57 EST 2011.
 */

package util.sedgewick;

import util.sorting.EquivalenceRelation;

/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann - Tübingen, Germany 
 * Niko Schenk - Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */

/*
 * http://www.cs.princeton.edu/~rs/cs226/sorts/UnionFind.java
 * Copyright © 2000–2013, Robert Sedgewick and Kevin Wayne. 
 */


import java.util.List;
import java.util.ArrayList;

public class UnionFind implements EquivalenceRelation {

    private int[] id;
    private int[] sz;
    private int offset;

    /**
     * UnionFind Constructor Construct a union find problem of size N
     *
     * @param N
     */
    public UnionFind(int lo, int hi) {
        int N = hi - lo + 1;
        offset = lo;
        id = new int[N];
        sz = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }

    /**
     * Find:
     *
     * @param x the value to be dereferenced
     * @return the representative of the set containing x
     */
    private int find(int x) {
        while (x != id[x]) {
            x = id[x];
        }
        return x;
    }

    /**
     * test equivalence
     *
     * @param p
     * @param q
     * @return true if p and q are in the same set
     */
    @Override
    public boolean equivalent(int p, int q) {
        return (find(p - offset) == find(q - offset));
    }

    /**
     * unite: put p and q into the same set
     *
     * @param p
     * @param q
     */
    @Override
    public void unite(int p, int q) {
        int i = find(p - offset);
        int j = find(q - offset);
        if (i == j) {
            return;
        }
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        } else {
            id[j] = i;
            sz[i] += sz[j];
        }
    }

    @Override
    public List<Integer> singletons() {
        List<Integer> result = new ArrayList<Integer>();
        for (int i = 0; i < id.length; i++) {
            if (id[i] == i && sz[i] == 1) {
                result.add(i + offset);
            }
        }
        return result;
    }
}
